#include <iostream>
#include <algorithm>
using namespace std;

#include "linearList.h"

/*==============================顺序表操作===================================*/

//初始化顺序表
sequenceList::sequenceList(const int& capacity, const int& size, float arr[]) :maxCapacity(capacity), curNumberOfItem(size) {
    myList = new float[maxCapacity];
    if (arr != nullptr && size > 0) {
        for (int i = 0; i < size; i++) {
            myList[i] = arr[i];
        }
    }
    curNumberOfItem = size;
}

//销毁顺序表
sequenceList::~sequenceList() {
    delete[]myList;
}

//尾插元素
bool sequenceList::addItem(const float& elem) {
    if (curNumberOfItem >= maxCapacity) {
        return false;
    }
    myList[curNumberOfItem++] = elem;
    return true;
}

//插入元素
bool sequenceList::insertItem(const int& index, const float& elem) {
    if (index<0 || index>curNumberOfItem) {
        return false;
    }
    if (curNumberOfItem >= maxCapacity) {
        return false;
    }
    for (int i = curNumberOfItem; i > index; i--) {
        myList[i] = myList[i - 1];
    }
    myList[index] = elem;
    curNumberOfItem++;
    return true;
}

//删除元素
int sequenceList::deleteItem(const float& elem) {
    int pos = -1;
    for (int i = 0; i < curNumberOfItem; i++) {
        if (myList[i] == elem) {
            pos = i;
            break;
        }
    }
    if (pos != -1) {
        for (int i = pos; i < curNumberOfItem - 1; i++) {
            myList[i] = myList[i + 1];
        }
        curNumberOfItem--;
    }
    return pos;
}

//查找元素（按位）
bool sequenceList::locate(const int& index, float& val) {
    if (index<0 || index>curNumberOfItem - 1) {
        return false;
    }
    val = myList[index];
    return true;
}

//查找元素（按值）
int sequenceList::locate(const float& val) {
    int pos = -1;
    for (int i = 0; i < curNumberOfItem; i++) {
        if (myList[i] == val) {
            pos = i;
            break;
        }
    }
    return pos;
}

//反转顺序表
void sequenceList::reverse() {
    if (myList == nullptr) {
        return;
    }
    for (int i = 0; i < curNumberOfItem / 2; i++) {
        float temp = myList[i];
        myList[i] = myList[curNumberOfItem - i - 1];
        myList[curNumberOfItem - i - 1] = temp;
    }
}

//顺序表打印
void sequenceList::print()
{
    cout << curNumberOfItem << ":";

    for(int i = 0; i < curNumberOfItem-1; i++)
    {
        cout << myList[i] << ",";
    }

    cout << myList[curNumberOfItem-1] << endl;
}

/*============================结点操作============================*/
//初始化无值结点
listNode::listNode():data(0.0f),next(NULL) {}

//初始化有值结点
listNode::listNode(float nodeData, listNode* succ): data(nodeData), next(succ) {}

// 节点析构函数
listNode::~listNode() {}

/*============================链表操作============================*/

//初始化链表(无初始值)
linkList::linkList() :firstNode(new listNode), lastNode(firstNode), listSize(0) {}

//初始化链表(有初始值)
linkList::linkList(const int& size, float arr[]) :firstNode(new listNode), lastNode(firstNode), listSize(0) {
    if (arr && size > 0) {
        for (int i = 0; i < size; i++) {
            tailInsertItem(arr[i]);
        }
    }
}

//销毁链表
linkList::~linkList() {
    if (!firstNode) {
        return;
    }
    listNode* current = firstNode->next;
    while (current != nullptr) {
        listNode* next = current->next;
        delete current;
        current = next;
    }
    delete firstNode;
}

//按值头插
bool linkList::headInsertItem(const float& elem) {
    listNode* p = new listNode(elem, firstNode->next);
    if (p == nullptr) {
        return false;
    }
    firstNode->next = p;
    if (listSize == 0) {
        lastNode = p;
    }
    listSize++;
    return true;
}

//按值尾插
bool linkList::tailInsertItem(const float& elem) {
    listNode* p = new listNode(elem, nullptr);
    if (p == nullptr) {
        return false;
    }
    if (listSize == 0) {
        firstNode->next = p;
        lastNode = p;
    }
    else {
        lastNode->next = p;
        lastNode = p;
    }
    listSize++;
    return true;
}

//插入特定位置
int linkList::insertItem(const int& index, const float& elem) {
    if (index<0 || index>listSize) {
        return -1;
    }
    curNode = firstNode;
    for (int i = 0; i < index; i++) {
        curNode = curNode->next;
    }
    listNode* p = new listNode(elem, curNode->next);
    curNode->next = p;
    if (index == listSize) {
        lastNode = p;
    }
    listSize++;
    return index;
}

//按值删除
int linkList::deleteItem(const float& val) {
    int index = -1;
    curNode = firstNode;
    for (int i = 0; i < listSize; i++) {
        if (curNode->next->data == val) {
            index = i;
            break;
        }
        curNode = curNode->next;
    }
    if (index != -1) {
        listNode* p = curNode->next;
        curNode->next = p->next;
        if (p == lastNode) {
            lastNode = curNode;
        }
        listSize--;
        delete p;
    }
    return index;
}

//按位查找
bool linkList::locate(const int& index, float& val) {
    if (index<0 || index>listSize - 1) {
        return false;
    }
    curNode = firstNode->next;
    for (int i = 0; i < index; i++) {
        curNode = curNode->next;
    }
    val = curNode->data;
    return true;
}

//按值查找
int linkList::locate(const float& val) {
    int index = -1;
    curNode = firstNode->next;
    for (int i = 0; i < listSize; i++) {
        if (curNode->data == val) {
            index = i;
            break;
        }
        curNode = curNode->next;
    }
    return index;
}

//升序
void linkList::ascendingOrder() {
    if (listSize <= 1) return;
    float* tempArray = new float[listSize];
    listNode* current = firstNode->next;
    for (int i = 0; i < listSize; ++i) {
        tempArray[i] = current->data;
        current = current->next;
    }
    for (int i = 0; i < listSize - 1; ++i) {
        for (int j = 0; j < listSize - i - 1; ++j) {
            if (tempArray[j] > tempArray[j + 1]) {
                swap(tempArray[j], tempArray[j + 1]);
            }
        }
    }
    current = firstNode;
    for (int i = 0; i < listSize; ++i) {
        current->next->data = tempArray[i];
        current = current->next;
    }
    lastNode = current;
    delete[] tempArray;
}

//倒排
void linkList::reverse() {
    if (listSize <= 1) {
        return;
    }
    listNode* prev = nullptr;
    listNode* current = firstNode->next;
    listNode* next = nullptr;
    while (current != nullptr) {
        next = current->next;
        current->next = prev;
        prev = current;
        current = next;
    }
    lastNode = firstNode->next;
    firstNode->next = prev;
    lastNode->next = nullptr;
}

//链表打印
void linkList::print()
{
    curNode = firstNode;

    cout << listSize << ":";

    while(curNode != lastNode)
    {
        if(curNode->next == lastNode)
            cout << curNode->next->data << endl;
        else
        {
            cout << curNode->next->data << ",";
        }
        
        
        curNode = curNode->next;
    }
}

void merge(linkList& alist, linkList& blist) {
    if (blist.firstNode->next == nullptr) goto T;
    alist.lastNode->next = blist.firstNode->next;
    alist.lastNode = blist.lastNode;
    alist.listSize += blist.listSize;    
    T:
    float* tempArray = new float[alist.listSize];
    listNode* current = alist.firstNode->next;
    for (int i = 0; i < alist.listSize; i++) {
        tempArray[i] = current->data;
        current = current->next;
    }
    for (int i = 0; i < alist.listSize - 1; ++i) {
        for (int j = 0; j < alist.listSize - i - 1; ++j) {
            if (tempArray[j] < tempArray[j + 1]) {
                swap(tempArray[j], tempArray[j + 1]);
            }
        }
    }
    current = alist.firstNode->next;
    for (int i = 0; i < alist.listSize; ++i) {
        current->data = tempArray[i];
        current = current->next;
    }
    delete[] tempArray;
}